import java.util.ArrayList;
import java.util.Arrays;

import java.util.HashMap;
import java.util.Map;


public class Leetcode {
}

//leetcode:354:俄罗斯套娃信件问题
class Solution1 {
    public int maxEnvelopes(int[][] envelopes) {
        //重写排序+贪心+二分
        //如果左端点不等按照左端点从小到大排序，如果相等按照右端点从大到小排序
        int n = envelopes.length;
        Arrays.sort(envelopes,(a, b) -> {
            return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
        });

        //将能进行套娃的信封放入集合中
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(envelopes[0][1]);
        for(int i = 1; i < n; i++){
            //按照右端点大小进行放入
            int b = envelopes[i][1];
            //如果集合中最后一个位置的值小于此时的b就将b直接放入到集合中
            if(b > ret.get(ret.size()-1)){
                ret.add(b);
            }else{
                //如果b小于集合的最后一个位置，就
                int left = 0, right = ret.size()-1;
                while(left < right){
                    int mid = (left + right) / 2;
                    if(ret.get(mid) < b){
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                ret.set(left,b);
            }
        }
        return ret.size();
    }
}


//leetcode:1262:可被三整除的最大和

class Solution2 {
    public int maxSumDivThree(int[] nums) {
        int INF = 0x3f3f3f3f;
        int sum = 0, x1 = INF,x2 =INF,y1 = INF ,y2 = INF;
        for(int x : nums){
            //计算总和
            sum += x;
            //如果模3余1
            if(x % 3 == 1){
                //如果小于x1,更新x1和x2
                if(x < x1){
                    x2 = x1;
                    x1 = x;
                }else if(x < x2){//只小于x2但大于x1，就更新x2
                    x2 = x;
                }
                //如果模3余2
            }else if(x % 3 == 2){
                //如果小于y1,更新y1和y2
                if(x < y1){
                    y2 = y1;
                    y1 = x;
                }else if(x < y2){//只小于y2但大于y1，就更新y2
                    y2 = x;
                }
            }
        }
        //如果模3为0直接返回
        if(sum % 3 == 0) return sum;
            //如果模3余1,让和减去一个余1的或两个余2的取它们的最大值
        else if(sum % 3 == 1) return Math.max(sum-x1,sum-y1-y2);
            //同理
        else return Math.max(sum-y1,sum-x1-x2);

    }

}

//leetcode:1054:距离相等的条形码
class Solution3 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        //创建一个哈希表
        Map<Integer,Integer> hash = new HashMap<>();
        int maxValue = 0, maxcount = 0;
        for(int x : barcodes){
            //记录每个数的出现个数
            hash.put(x,hash.getOrDefault(x,0)+1);
            //更新最大个数和对应的值
            if(maxcount < hash.get(x)){
                maxValue = x;
                maxcount = hash.get(x);
            }
        }
        int n = barcodes.length;
        int[] ret = new int[n];
        int index = 0;
        //让个数最多的元素先放入，按偶数位置存放
        for(int i = 0; i < maxcount; i++){
            ret[index] = maxValue;
            index += 2;
        }
        //存放完后移除这个元素
        hash.remove(maxValue);

        //按照空位依次放剩下的元素
        for(int x : hash.keySet()){
            for(int i = 0; i < hash.get(x); i++){
                //如果要放的位置超过了数组长度，就从1位置往后开始存放
                if(index >= n) index = 1;
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
    }
}
